163A - Substring and Subsequence - CodeForces Solution

#include <iostream>
#include <cstring>
#define int long long
using namespace std;

const int mod = 1e9 + 7;
int sum, len1, len2, dp[5005][5005];
string a, b;

signed main()
{
	while(cin >> a >> b)
	{
		sum = 0, memset(dp, 0, sizeof dp), len1 = a.size(), len2 = b.size();
		for(int i = 0; i <= len1 - 1; i++)
			for(int j = 0; j <= len2 - 1; j++)
				dp[i + 1][j + 1] = (dp[i + 1][j] + (a[i] == b[j]) * (dp[i][j] + 1)) % mod;
		for(int i = 1; i <= len1; i++)
			sum = (sum + dp[i][len2]) % mod;
		cout << sum << endl;
	}
	return 0;
}